package com.zyk.leetcode;

import com.zyk.util.TreeUtil;

import java.util.ArrayList;

/**
 * @author zhangsan
 * @date 2021/4/9 15:29
 */
public class M0405 {

    // https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/
    // 二叉搜索树, 左树都比自己小, 右树比自己大.
    public static boolean isValidBST(TreeNode root) {
        return process(root).isBST;
    }

    private static Info process(TreeNode root) {
        if(root == null) {
            return new Info(Long.MIN_VALUE, Long.MAX_VALUE, true);
        }
        Info li = process(root.left);
        Info ri = process(root.right);
        long max = Math.max(root.val, Math.max(li.max, ri.max));
        long min = Math.min(root.val, Math.min(li.min, ri.min));
        boolean isBST = true;
        if(!li.isBST || !ri.isBST || li.max >= root.val || ri.min <= root.val)
            isBST = false;
        return new Info(max, min, isBST);
    }

    public static boolean isValidBST2(TreeNode head) {
        if(head == null) { return true; }
        ArrayList<TreeNode> list = new ArrayList<>();
        in(head, list);

        for (int i = 0; i < list.size() - 1; i++) {
            if(list.get(i + 1).val <= list.get(i).val ) {
                return false;
            }
        }
        return true;
    }

    private static void in(TreeNode head, ArrayList<TreeNode> list) {
        if(head == null) { return; }
        in(head.left, list);
        list.add(head);
        in(head.right, list);
    }

    private static class Info {
        long max;
        long min;
        boolean isBST;
        public Info(long max, long min, boolean isBST) {
            this.max = max;
            this.min = min;
            this.isBST = isBST;
        }
    }

    // for test
    public static void main(String[] args) {
        Integer[] treeInfo = {
                2147483647
        };
        TreeNode root = TreeUtil.generateTreeByArr(treeInfo);
        System.out.println(isValidBST(root));
    }

}
